﻿// In the combinatorial mathematics, the Catalan numbers are calculated by the following formula:
// CatalanN = (2n)! / ( (n+1)!n! )
// The first Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 
// 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324...

// THIIS IS 9th AND 10th PROBLEM FROM THE HOMEWORK AT THE SAME TIME

using System;
using System.Numerics;

class CatalanNumbers
{
    static void Main()
    {
        Console.Write("Enter N : ");
        BigInteger numberN = BigInteger.Parse(Console.ReadLine());

        BigInteger numerator = 1;
        BigInteger denominator = 1;

        for (int i = 1; i <= numberN; i++)
        {
            numerator *= (numberN + i);
            denominator *= i;
        }

        // the numerator is prodct from (n+2) to 2*n, but the loop for makes 1 more cycle; 
        // so I divide the numerator by (n+1) to get its correct value
        BigInteger result = (numerator / (numberN + 1)) / denominator;
        Console.WriteLine("Number {0} of the Catalan numbers is {1}", numberN, result);
    }
}
